﻿using System;
using System.Collections.Generic;
using System.IO;

namespace luozhuangSLLZSS
{
    public class LZSSoutstreamputStream
    {

        private static int N = 4096;        /* 4k buffers for LZ compression */
        private static int F = 16;          /* upper limit for LZ match length */
        private static int THRESHOLD =2;   /* LZ encode string into pos and length 
                       if match size is greater than this */


        /* stuff for doing LZ compression */
        int state;                       /* where have we got to in the pack? */
        int i, len, r, s;
        byte c;
        int last_match_length, code_buf_ptr;
        byte mask;
        byte[] code_buf;
        int match_position;
        int match_length;
        int[] lson;                   /* left children, */
        int[] rson;                 /* right children, */
        int[] dad;                    /* and parents, = binary search trees */
        Stream outstream;
        byte[] text_buf;            /* ring buffer, with F-1 extra bytes 
                       for string comparison */

        public LZSSoutstreamputStream(Stream outstream)
        {
            this.outstream = outstream;
            code_buf = new byte[17];
            lson = new int[N + 1];
            rson = new int[N + 257];
            dad = new int[N + 1];
            text_buf = new byte[N + F - 1];
            state = 0;
        }
/* pack_inittree: 
 *  For i = 0 to N-1, rson[i] and lson[i] will be the right and left  
 *  children of node i. These nodes need not be initialized. Also, dad[i]  
 *  is the parent of node i. These are initialized to N, which stands for  
 *  'not used.' For i = 0 to 255, rson[N+i+1] is the root of the tree for  
 *  strings that begin with character i. These are initialized to N. Note  
 *  there are 256 trees. 
 */  
      
private  void inittree()  
{  
   int i;  
  
   for (i=N+1; i<=N+256; i++)  
      rson[i] = N;  
  
   for (i=0; i<N; i++)  
      dad[i] = N;  
}  
  
/* pack_insertnode: 
 *  Inserts a string of length F, text_buf[r..r+F-1], into one of the trees  
 *  (text_buf[r]'th tree) and returns the longest-match position and length  
 *  via match_position and match_length. If match_length = F, then removes  
 *  the old node in favor of the new one, because the old one will be  
 *  deleted sooner. Note r plays double role, as tree node and position in  
 *  the buffer.  
 */  
private  void pack_insertnode(int r)  
{  
   int i, p, cmp;  
//   unsigned char *key;   
//   unsigned char *text_buf = text_buf;   
  
   cmp = 1;  
//   key = &text_buf[r];   
   p = N + 1 + ( text_buf[r] & 0xFF);  
   rson[r] = lson[r] = N;  
   match_length = 0;  
  
   for (;;) {  
  
      if (cmp >= 0) {  
     if (rson[p] != N)  
        p = rson[p];  
     else {  
        rson[p] = r;  
        dad[r] = p;  
        return;  
     }  
      }  
      else {  
     if (lson[p] != N)  
        p = lson[p];  
     else {  
        lson[p] = r;  
        dad[r] = p;  
        return;  
     }  
      }  
  
      for (i = 1; i < F; i++)  
     if ((cmp = (text_buf[r+i] & 0xff) - (text_buf[p + i]) & 0xFF) != 0) /* SIGN BUG? */  
        break;  
  
      if (i > match_length) {  
     match_position = p;  
     if ((match_length = i) >= F)  
        break;  
      }  
   }  
  
   dad[r] = dad[p];  
   lson[r] = lson[p];  
   rson[r] = rson[p];  
   dad[lson[p]] = r;  
   dad[rson[p]] = r;  
   if (rson[dad[p]] == p)  
      rson[dad[p]] = r;  
   else  
      lson[dad[p]] = r;  
   dad[p] = N;                 /* remove p */  
}  
  
/* pack_deletenode: 
 *  Removes a node from a tree. 
 */  
private  void pack_deletenode(int p )  
{  
   int q;  
  
   if (dad[p] == N)  
      return;     /* not in tree */  
  
   if (rson[p] == N)  
      q = lson[p];  
   else  
      if (lson[p] == N)  
     q = rson[p];  
      else {  
     q = lson[p];  
     if (rson[q] != N) {  
        do {  
           q = rson[q];  
        } while (rson[q] != N);  
        rson[dad[q]] = lson[q];  
        dad[lson[q]] = dad[q];  
        lson[q] = lson[p];  
        dad[lson[p]] = q;  
     }  
     rson[q] = rson[p];  
     dad[rson[p]] = q;  
      }  
  
   dad[q] = dad[p];  
   if (rson[dad[p]] == p)  
      rson[dad[p]] = q;  
   else  
      lson[dad[p]] = q;  
  
   dad[p] = N;  
}  
  
/* pack_write: 
 *  Called by flush_buffer(). Packs size bytes from buf, using the pack  
 *  information contained in dat. Returns 0 on success. 
 */  
private  void pack_write(int size, byte[] buf, int bufi,bool last) 
{  
 // System.outstream.println("Entering state="+state);   
   bool skipme=false;  
   if(state==0)  
   {  
             code_buf[0] = 0;  
         /* code_buf[1..16] saves eight units of code, and code_buf[0] works 
         as eight flags, "1" representing that the unit is an unencoded 
         letter (1 byte), "0" a position-and-length pair (2 bytes). 
         Thus, eight units require at most 16 bytes of code. */  
  
              code_buf_ptr = mask = 1;  
  
              s = 0;  
              r = N - F;  
              inittree();  
          len = 0;  
   } else if(state==1) len++;  
  
   if(state!=2)  
   {  
   while ( (len < F) && (size > 0)) {  
//   for (; (len < F) && (size > 0); len++) x   
      text_buf[r+len] = buf[bufi++];  
      if (--size == 0) {  
     if (!last) {  
        state = 1;  
        return;   
     }  
      }  
      pos1:  
      len++;  
   }  
  
   if (len == 0) return;  
  
   for (i=1; i <= F; i++)  
      pack_insertnode(r-i);  
        /* Insert the F strings, each of which begins with one or 
           more 'space' characters. Note the order in which these 
           strings are inserted. This way, degenerate trees will be 
           less likely to occur. */  
  
   pack_insertnode(r);  
        /* Finally, insert the whole string just read. match_length 
           and match_position are set. */  
   } /* state!=2 */  
    else  
    {  
        skipme=true;  
    }  
  
   do {  
      if(skipme==false)  
      {  
      if (match_length > len)  
     match_length = len;  /* match_length may be long near the end */  
  
      if (match_length <= THRESHOLD) {  
     match_length = 1;  /* not long enough match: send one byte */  
     code_buf[0] |= mask;    /* 'send one byte' flag */  
     code_buf[code_buf_ptr++] = text_buf[r]; /* send uncoded */  
      }  
      else {  
     /* send position and length pair. Note match_length > THRESHOLD */  
     code_buf[code_buf_ptr++] = (byte) match_position;  
     code_buf[code_buf_ptr++] = (byte)  
                     (((match_position >>  4) & 0xF0) |  
                      (match_length - (THRESHOLD + 1)));  
      }  
  
      if ((mask <<= 1) == 0) {               /* shift mask left one bit */  
                 /* send at most 8 units of */  
                 /* code together */   
          outstream.Write(code_buf,0,code_buf_ptr);  
        code_buf[0] = 0;  
        code_buf_ptr = mask = 1;  
      }  
  
      last_match_length = match_length;  
      i=0;  
      } /*skipme*/  
  
      /* jak se dostat dovnitr? */  
      /* 
      if(skipme==true && ((i < last_match_length) && (size > 0))== false) 
          { 
              System.outstream.println("Can not get inside.... size="+size); 
              // skipme=false; 
          } 
      */  
      for(;;) {  
    //  for (; (i < last_match_length) && (size > 0); i++)    
     if(skipme==false)  {  
         if( (i >= last_match_length) || (size <= 0) ) break;  
       c = buf[bufi++];  
           if (--size == 0) {  
          if (!last) {  
              state = 2;  
              return;  
          }  
       }  
     }  
       else {skipme=false;/* System.outstream.println("Skip in")*/;}  
     pos2:  
     pack_deletenode(s);    /* delete old strings and */  
     text_buf[s] = c;      /* read new bytes */  
     if (s < F-1)  
        text_buf[s+N] = c; /* if the position is near the end of 
                       buffer, extend the buffer to make 
                       string comparison easier */  
     s = (s+1) & (N-1);  
     r = (r+1) & (N-1);         /* since this is a ring buffer, 
                       increment the position modulo N */  
  
     pack_insertnode(r);    /* register the string in 
                       text_buf[r..r+F-1] */  
         i++;  
      }   
        
      while (i++ < last_match_length) {   /* after the end of text, */  
     pack_deletenode(s);          /* no need to read, but */  
     s = (s+1) & (N-1);               /* buffer may not be empty */  
     r = (r+1) & (N-1);  
     if (--len!=0)  
        pack_insertnode(r);   
      }  
  
   } while (len > 0);   /* until length of string to be processed is zero */  
  
   if (code_buf_ptr > 1) {         /* send remaining code */

       outstream.Write(code_buf, 0, code_buf_ptr);  
      return;  
   }  
   /* do not reset buffer */  
   // state = 0;   
}  
/* interface methods */  
  
       
        public void write(byte[] zz, int ofs, int sz)
        {
            pack_write(sz, zz, ofs, false);
        }



        public void close()
        {
            outstream.Close();
            code_buf = null;
            lson = null;
            rson = null;
            dad = null;
            text_buf = null;

        }

    }

}
